package cn.edu.nju.ws.sview.reasoning.schema;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import cn.edu.nju.ws.sview.cache.SubpropertyCache;

/**
 * 
 * @author ssgong
 *
 */
public class Subproperty {
	  private static Subproperty INSTANCE = null;
	   private Subproperty(){
	   }
	   
	   public static synchronized Subproperty getInstance(){
			if (INSTANCE == null) {
				INSTANCE = new Subproperty();
			}
			return INSTANCE;
	   }
	    /**
	     * given several properties , find the minimal ones of them(belong to them)
	     * @param properties
	     * @return may contain equivalent properties
	     * @throws Throwable 
	     */
	   public HashSet<Integer> getMinProperties(HashSet<Integer> properties) throws Throwable{
		   HashSet<Integer> result = new HashSet<Integer>();
		   HashMap<Integer, HashSet<Integer>> graph = new HashMap<Integer, HashSet<Integer>>();
		   for(Integer propertyID:properties){
			   HashSet<Integer> superSet = SubpropertyCache.getInstance().getSuperProperty(propertyID) ;
			   superSet.retainAll(properties) ;
			   graph.put(propertyID,superSet) ;
		   }
			HashMap<Integer, HashSet<Integer>> reverseGraph = new HashMap<Integer, HashSet<Integer>>();
			ArrayList<Integer> finish = new ArrayList<Integer>();
			HashSet<Integer> visited = new HashSet<Integer>();
			for(Integer shit :properties){
				if(!visited.contains(shit)){
				   firstDFS(shit,finish, graph,reverseGraph, visited);
				}
			}
			HashMap<Integer,HashSet<Integer>> scc = new HashMap<Integer,HashSet<Integer>>();
			visited.clear();
			for (int i = finish.size() - 1; i >= 0; i--) {
				Integer propertyID= finish.get(i);
				if (!visited.contains(propertyID)){
					HashSet<Integer> set = secondDFS(propertyID, reverseGraph,  visited);
					for(Integer s:set){
						scc.put(s, set) ;
					}
				}
			}
		   for(Integer element:properties){
			   HashSet<Integer> set = scc.get(element) ;
	 		   if(!reverseGraph.containsKey(element)){
				   result.add(element) ;
			   }else {
				   if(!result.contains(element)){
					   HashSet<Integer> shit = new HashSet<Integer>();
					   for(Integer member:set){
						   if(reverseGraph.containsKey(member)){
							   shit.addAll(reverseGraph.get(member)) ;
						   }
					   }
					   if(set.containsAll(shit)){
						   result.addAll(set) ;
					   }
				   }
			   }
		   }
		   return result;
	   }
	   
	   /**
	    * given several properties , find the minimal superproperties of them
	    * @param properties
	    * @return may contain equivalent properties
	 * @throws Throwable 
	    */
	   public HashSet<Integer> getMinimalSuperProperties(HashSet<Integer> properties) throws Throwable{
		   HashSet<Integer> superproperties = new HashSet<Integer>();
		   for(Integer element:properties){
			   HashSet<Integer> set = SubpropertyCache.getInstance().getSuperProperty(element) ;
			   set.add(element) ;
			   if(superproperties.size()>0){
				   superproperties.retainAll(set) ;
			   }else{
				   superproperties.addAll(set) ;
			   }
		   }
		   return getMinProperties(superproperties) ;
	   }
	   
	   
		private void firstDFS(Integer start,ArrayList<Integer> finish, HashMap<Integer, HashSet<Integer>> graph,
				HashMap<Integer, HashSet<Integer>> reverseGraph,
				HashSet<Integer> visited) {
			visited.add(start);
			Iterator<Integer> itor = graph.get(start).iterator();
			while (itor.hasNext()) {
				Integer  neighbor = itor.next();
				addEdge(reverseGraph, neighbor, start);
				if (!visited.contains(neighbor))
					firstDFS(neighbor,finish, graph,reverseGraph, visited);
			}
			finish.add(start);
		}

		private HashSet<Integer> secondDFS(Integer element,
				final HashMap<Integer, HashSet<Integer>> reverseGraph,
				HashSet<Integer> visited) {
			HashSet<Integer> result = new HashSet<Integer>();
			visited.add(element);
			if (reverseGraph.get(element) == null) {
				result.add(element) ;
				return result;
			}
			Iterator<Integer> itor = reverseGraph.get(element).iterator();
			while (itor.hasNext()) {
				Integer neighbour = itor.next();
				if (!visited.contains(neighbour)){
					HashSet<Integer> set = secondDFS(neighbour, reverseGraph,  visited);
					result.addAll(set) ;
				}
			}
			result.add(element);
			return result;
		}

		private void addEdge(HashMap<Integer, HashSet<Integer>> reverseGraph,
				Integer source, Integer obj) {
			if (!reverseGraph.containsKey(source)) {
				HashSet<Integer> list = new HashSet<Integer>();
				list.add(obj);
				reverseGraph.put(source, list);
			} else {
				HashSet<Integer> list = reverseGraph.get(source);
				list.add(obj);
			}
			return;
		}
		
}
